/**
 * Node抽象类
 * 存放数据是Node最基本的功能
 */
template <typename DT>
class Node
{
public:
    /// 纯虚函数规范子类的行为，用于为存放数据的私有成员属性提供接口
    virtual DT getData()const =0;
    virtual void setData()=0;
};

/**
 * 二叉树抽象类
 * 二叉树最基本的功能为插入、删除和查找
 * 基于左值和右值提供了两个版本的函数
 */
template <typename DT>
class BinaryTree
{
public:
    virtual void insert(const DT & _data)=0;
    virtual void insert(DT && _data)=0;
    virtual void remove(const DT &  _data)=0;
    virtual bool contains(const DT &  _data)const=0;
};

/**
 * 二叉搜索树是一种二叉树
 * 从基类BinaryTree继承
 */
template <typename DT>
class BinarySearchTree:public BinaryTree<DT>
{
public:
    BinarySearchTree();
    BinarySearchTree(const BinarySearchTree & rhs);
    BinarySearchTree(BinarySearchTree && rhs);
    ~BinarySearchTree();
    BinarySearchTree & operator=(const BinarySearchTree & rhs);
    BinarySearchTree & operator=(BinarySearchTree && rhs);
    
    /// 基类的纯虚函数在派生类中必须实现
    virtual void insert(const DT & _data);
    virtual void insert(DT && _data);
    virtual void remove(const DT &  _data);
    virtual bool contains(const DT &  _data)const;
    
    const DT & findMin();
    const DT & findMax();
    bool isEmpty()const;
    void makeEmpty();
    void printTree()const;
private:
    /**
     * 二叉树节点是节点
     * 从基类Node继承
     */
    class BSTNode:public Node<DT>
    {
    public:
	BSTNode(const DT & _data,BSTNode * lt,BSTNode * rt);
	BSTNode(DT && _data,BSTNode * lt,BSTNode * rt);
	
	virtual DT getData()const;
	virtual void setData();
	/// 指向左子树的根节点
        BSTNode * left;
	/// 指向右子树的根节点
	BSTNode * right;
    private:
	DT data;
    };
    /// 指向根节点
    BSTNode * root;
    
    BSTNode * clone(BSTNode * _t)const;
};

/**
 * AvlTree是一种自平衡二叉搜索树
 * 从类BinarySearchTree继承
 */
template <typename DT>
class AvlTree:public BinarySearchTree<DT>
{
public:
    AvlTree();
    AvlTree(const AvlTree & rhs);
    AvlTree(AvlTree && rhs);
    ~AvlTree();
    AvlTree & operator=(const AvlTree & rhs);
    AvlTree & operator=(AvlTree && rhs);
    
    virtual void insert(const DT & _data);
    virtual void insert(DT && _data);
    virtual void remove(const DT &  _data);
    virtual bool contains(const DT &  _data)const;

    const DT & findMin();
    const DT & findMax();
    bool isEmpty()const;
    void makeEmpty();
    void printTree()const;
private:
    /**
     * AvlNode是节点
     * 从基类Node继承
     */
    class AvlNode:public Node<DT>
    {
    public:
	AvlNode(const DT &  _data,AvlNode * lt, AvlNode * rt,int h=0);
	AvlNode(DT && _data,AvlNode * lt, AvlNode * rt,int h=0);
	
	virtual DT getData()const;
	virtual void setData();
	/// 记录节点高度，用于树的平衡
	int height;
	/// 指向左子树根节点
	AvlNode * left;
	/// 指向右子树根节点
	AvlNode * right;
    private:
	DT data;
    };
    /// 指向根节点
    AvlNode * root;
    /** 
     * 用于平衡AvlTree
     * 在每次插入删除时调用
     * @param _t 指针引用类型，可以在函数中修改指针指向
     */
    void balance(AvlNode * & _t);
    /// 左子树单旋，调整树的结构
    void rotateWithLeftChild(AvlNode * & _t);
    /// 右子树单旋，调整树的结构
    void rotateWithRightChild(AvlNode * & _t);
    /// 左子树双旋，调整树的结构
    void doubleWithLeftChild(AvlNode * & _t);
    /// 右子树双旋，调整树的结构
    void doubleWithRightChild(AvlNode * & _t);

    int height(AvlNode * _t)const;
    int max(int lhs,int rhs)const;
    AvlNode * clone(AvlNode * _t)const;
};

/**
 * SplayTree是一种自平衡二叉搜索树
 * 从类BinarySearchTree继承
 */
template <typename DT>
class SplayTree:public BinarySearchTree<DT>
{
public:
    SplayTree();
    SplayTree(const SplayTree & rhs);
    SplayTree(SplayTree && rhs);
    ~SplayTree();
    SplayTree & operator=(const SplayTree & rhs);
    SplayTree & operator=(SplayTree && rhs);
    
    virtual void insert(const DT & _data);
    virtual void insert(DT && _data);
    virtual void remove(const DT &  _data);
    virtual bool contains(const DT &  _data)const;

    const DT & findMin();
    const DT & findMax();
    bool isEmpty()const;
    void makeEmpty();
    void printTree()const;
private:
    /**
     * SNode是节点
     * 从基类Node继承
     */
    class SNode:public Node<DT>
    {
    public:
	SNode(const DT &  _data,SNode * lt,SNode * rt);
	SNode(DT &&  _data,SNode * lt,SNode * rt);
	
	virtual DT getData()const;
	virtual void setData();
	/// 指向左子树根节点
	SNode * left;
	/// 指向右子树根节点
	SNode * right;
    private:
	DT data;
    };
    /// 指向根节点
    SNode * root;
    /// 指向开辟在堆区的空节点，用于初始化伸展树和伸展操作
    SNode * nullNode;
    
    /** 
     * 伸展树的伸展操作
     * 在节点被访问后重构树
     * 使树变得更加平衡
     */
    void splay(const DT & _data,SNode * & _t);
    /// 左子树单旋，调整树的结构
    void rotateWithLeftChild(SNode * & _t);
    /// 右子树单旋，调整树的结构
    void rotateWithRightChild(SNode * & _t);

    void reclaimMemory(SNode * _t);
    SNode * clone(SNode * _t)const;
};
